|
In the mathematical field of graph theory, the Laplacian matrix, sometimes called admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be used to find many other properties of the graph. Cheeger's inequality from Riemannian geometry has a discrete analogue involving the Laplacian matrix; this is perhaps the most important theorem in spectral graph theory and one of the most useful facts in algorithmic applications. It approximates the sparsest cut of a graph through the second eigenvalue of its Laplacian. ==Definition== Given a simple graph ''G'' with ''n'' vertices, its Laplacian matrix is defined as: : where ''D'' is the degree matrix and ''A'' is the adjacency matrix of the graph. In the case of directed graphs, either the indegree or outdegree might be used, depending on the application. The elements of are given by : where deg(''vi'') is degree of the vertex ''i''. The symmetric normalized Laplacian matrix is defined as:〔 : , The elements of The random-walk normalized Laplacian matrix is defined as: : The elements of 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Laplacian matrix」の詳細全文を読む スポンサード リンク
|